一道后缀自动机的板题。
我们从根结点开始匹配,如果有转移就将
不然就顺着后缀链接向上跳,直到找到有转移的点,用 继续匹配。(后缀链接一定是它的子串,也能被匹配)。
如果没有跳到合适的点就从根重新匹配。
最后选取最大的就可以了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 2 * 250000 , MAXC = 26;
struct Suffix_Automaton {
int Size , Last , Maxlen[ MAXN + 5 ];
int Trans[ MAXN + 5 ][ MAXC + 5 ] , Link[ MAXN + 5 ];
Suffix_Automaton( ) { Size = Last = 1; }
void Copy( int u , int v ) {
for( int i = 1 ; i <= MAXC ; i ++ )
Trans[ u ][ i ] = Trans[ v ][ i ];
}
void Extend( int chr ) {
int Newnode = ++ Size , u = Last;
Maxlen[ Newnode ] = Maxlen[ u ] + 1;
for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
Trans[ u ][ chr ] = Newnode;
if( !u ) Link[ Newnode ] = 1;
else {
int v = Trans[ u ][ chr ];
if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
else {
int w = ++ Size;
Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
Link[ w ] = Link[ v ];
Link[ v ] = Link[ Newnode ] = w;
}
}
Last = Newnode;
}
void Build( char *str ) {
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
Extend( str[ i ] - 'a' + 1 );
}
int Calc( char *str ) {
int len = strlen( str );
int Ans = 0 , tot = 0 , u = 1;
for( int i = 0 ; i < len ; i ++ ) {
int chr = str[ i ] - 'a' + 1;
if( Trans[ u ][ chr ] ) {
tot ++;
u = Trans[ u ][ chr ];
}
else {
for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] );
if( !u ) tot = 0 , u = 1;
else {
tot = Maxlen[ u ] + 1;
u = Trans[ u ][ chr ];
}
}
Ans = max( Ans , tot );
}
return Ans;
}
}SAM;
char str[ 3 ][ MAXN + 5 ];
int main( ) {
for( int i = 1 ; i <= 2 ; i ++ )
scanf("%s",str[ i ]);
SAM.Build( str[ 1 ] );
printf("%d", SAM.Calc( str[ 2 ] ) );
return 0;
}